/*
==================================================================
* 版权所有 © 2025 CaryXiong
* Copyright (C) 2025 CaryXiong(a1816101108@outlook.com)
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
===================================================================
*/


#include<iostream>
#include<cmath>
using namespace std;

template<class DataType>
class symArray{
    // 对称矩阵的压缩算法
    public:
        symArray(DataType *data, int Array_Len);
        void Print_Extressed();
        
    private:
        DataType *SA;
        int Array_Len, SA_Len;
};

template<class DataType>
symArray<DataType> :: symArray(DataType *data, int Array_Len){
    this->Array_Len = Array_Len;
    SA_Len = ((1+Array_Len)*Array_Len)/2;
    SA = new DataType[SA_Len];
    int count = 0;

    for(int i=0; i<Array_Len; i++){
        for(int j=0; j<=i; j++){
            SA[count++] = *(data + i*Array_Len + j);
        }
    }

    cout << "压缩所得的一维数组：" << endl;
    for(int i=0; i<SA_Len; i++){
        cout << SA[i] << '\t';
    }
    cout << endl;
}

template<class DataType>
void symArray<DataType> :: Print_Extressed(){
    // int Array_Len = (sqrt(SA_Len*8+1)-1)/2;
    
    for(int i=0; i<Array_Len; i++){
        for(int j=0; j<Array_Len; j++){
            if(i>=j) cout << SA[(i*(i+1))/2+j] << '\t';
            else cout << SA[(j*(j+1))/2+i] << '\t';
        }
        cout << endl;
    }
}













template<class DataType>
class triArray{
    // 三角矩阵的压缩算法
    public:
        triArray(DataType *data, int Array_Len, int statue);
        void Print_Extressed();
        
    private:
        DataType *SA;
        int SA_Len, Array_Len, repeatNum, statue;
};

template<class DataType>
triArray<DataType> :: triArray(DataType *data, int Array_Len, int statue){
    // statue 为1时 下三角
    //        为2时 上三角
    this->Array_Len = Array_Len;
    this->statue = statue;
    SA_Len = ((1+Array_Len)*Array_Len)/2;
    SA = new DataType[SA_Len];
    int count = 0;

    if(statue == 1) repeatNum = *(data + Array_Len-1);
    else repeatNum = *(data + (Array_Len-1)*Array_Len);

    if(statue == 1){
        for(int i=0; i<Array_Len; i++){
            for(int j=0; j<=i; j++){
                SA[count++] = *(data + i*Array_Len + j);
            }
        }
    }else{
        for(int i=0; i<Array_Len; i++){
            for(int j=i; j<Array_Len; j++){
                SA[count++] = *(data + i*Array_Len + j);
            }
        }
    }

    cout << "压缩所得的一维数组：" << endl;
    for(int i=0; i<SA_Len; i++){
        cout << SA[i] << '\t';
    }
    cout << endl;
}

template<class DataType>
void triArray<DataType> :: Print_Extressed(){
    for(int i=0; i<Array_Len; i++){
        for(int j=0; j<Array_Len; j++){
            if(statue == 1){
                if(i>=j){
                    cout << SA[(i*(i+1))/2+j] << '\t';
                }else{
                    cout << repeatNum << '\t';
                }
            }else{
                if(i>j){
                    cout << repeatNum << '\t';
                }else{
                    cout << SA[(i*(i+1))/2+j] << '\t';
                }
            }
        }
        cout << endl;
    }
}



















template<class DataType>
class diagArray{
    // 对角矩阵的压缩算法
    // 这里使用二维数组法进行压缩
    public:
        diagArray(DataType *data, int Array_Len, int diagNum, int direction);
        void Print_Extressed();
        
    private:
        DataType **SA;
        int Array_Len, diagNum;
};

template<class DataType>
diagArray<DataType> :: diagArray(DataType *data, int Array_Len, int diagNum, int direction){
    // direction 1:主对角线方向
    //           2:副对角线方向
    this->Array_Len = Array_Len;
    this->diagNum = diagNum;
    SA = new DataType*[Array_Len];
    int length = sizeof(SA);
    
    if(direction == 1){
        for(int i=1; i<Array_Len-1; i++){
            SA[i] = new DataType[diagNum];

            for(int j=i-1; j<i+diagNum-1; j++){
                SA[i][j-i+1] = *((int*)data + i*Array_Len + j);
            }
        }
        SA[0] = new DataType[diagNum];
        SA[Array_Len-1] = new DataType[diagNum];
        for(int i=0; i<diagNum; i++){
            SA[0][i] = *((int*)data + i);
            SA[Array_Len-1][i] = *((int*)data + Array_Len*Array_Len - diagNum + i);
        }
    }else{
        for(int i=1; i<Array_Len-1; i++){
            SA[i] = new DataType[diagNum];

            for(int j=i-1; j<i+diagNum-1; j++){
                SA[i][j-i+1] = *((int*)data + i*Array_Len + j);
            }
        }
        for(int i=0; i<diagNum; i++){
            SA[0][i] = *((int*)data + Array_Len - diagNum + i);
            SA[Array_Len-1][Array_Len+i-diagNum] = *((int*)data + (Array_Len-1)*Array_Len + i);
        }
    }



    cout << "使用二维数组法对该矩阵进行压缩" << endl;
    cout << "压缩所得的二维数组：" << endl;
    for(int i=0; i<5; i++){
        for(int j=0; j<3; j++){
            cout << SA[i][j] << '\t';
        }
        cout << endl;
    }
}

template<class DataType>
void diagArray<DataType> :: Print_Extressed(){
    int Result_Len = Array_Len;
    int num = diagNum;
    // int Result_Len = sizeof(SA)/sizeof(SA[0]);
    // int num = sizeof(SA[0])/sizeof(SA[0][0]);
    int a=sizeof(SA), b=sizeof(SA[0]), c=sizeof(SA[0][0]);
    if(SA[0][0] != 0){
        for(int i=0; i<Result_Len; i++){
            if(i==0){
                for(int m=0; m<Result_Len; m++){
                    if(m<num-1) cout << SA[i][m] << '\t';
                    else cout << '0' << '\t';
                }
                cout << endl;
                continue;
            }
            if(i==Result_Len-1){
                for(int m=0; m<Result_Len; m++){
                    if(m>num-1) cout << SA[i][m-num+1] << '\t';
                    else cout << '0' << '\t';
                }
                cout << endl;
                continue;
            }

            for(int m=0; m<i-1; m++) cout << '0' << '\t';
            for(int j=0; j<num; j++){
                cout << SA[i][j] << '\t';
            }
            for(int m=0; m<Result_Len-i+1-num; m++) cout << '0' << '\t';
            cout << endl;
        }
    }else{
        for(int i=0; i<Result_Len; i++){
            if(i==0){
                for(int m=0; m<Result_Len; m++){
                    if(m<num-1) cout << SA[i][m] << '\t';
                    else cout << '0' << '\t';
                }
                cout << endl;
                continue;
            }
            if(i==Result_Len-1){
                for(int m=0; m<Result_Len; m++){
                    if(m>num-1) cout << SA[i][m-num+1] << '\t';
                    else cout << '0' << '\t';
                }
                cout << endl;
                continue;
            }

            for(int m=0; m<i-1; m++) cout << '0' << '\t';
            for(int j=0; j<num; j++){
                cout << SA[i][j] << '\t';
            }
            for(int m=0; m<Result_Len-i+1-num; m++) cout << '0' << '\t';
            cout << endl;
        }
    }
}














template<class DataType>
struct element
{
    int row, col;
    DataType item;
};

template<class DataType>
struct OrthNode
{
    element<DataType> data;
    struct OrthNode *right=nullptr, *down=nullptr;
};


template<class DataType>
class sparArray_Link{
    // 稀疏矩阵压缩的十字链表实现方法
    public:
        sparArray_Link(DataType *data, int row, int col);
        DataType Get(int row, int col);

    private:
        OrthNode<DataType> *HA, *HB;
};

template<class DataType>
sparArray_Link<DataType> :: sparArray_Link(DataType *data, int row, int col){
    // 稀疏矩阵的十字链表实现方法
    HA = new OrthNode<DataType>[row];
    HB = new OrthNode<DataType>[col];
    OrthNode<DataType> *p;
    OrthNode<DataType> *q;

    for(int i=0; i<row; i++){
        p = &HA[i];
        for(int j=0; j<col; j++){
            q = &HB[j];
            while(q->down != nullptr) q = q->down;

            if(*((int*)data + i*col + j)){
                p->right = new OrthNode<DataType>;
                p = p->right;
                p->data.row = i+1;
                p->data.col = j+1;
                p->data.item = *((int*)data + i*col + j);

                q->down = p;
            }
        }
    }
}

template<class DataType>
DataType sparArray_Link<DataType> :: Get(int row, int col){
    OrthNode<DataType> *p = &HA[row-1];
    while(p->right != nullptr){
        p = p->right;
        if(p->data.col == col) return p->data.item;
    }
    return -1;
}









const int MaxTerm = 100;
template<class Datatype>
struct SparseArray
{
    element<Datatype> data[MaxTerm];
    int mu, nu, tu;
};


template<class Datatype>
class sparArray_Tuple{
    public:
        sparArray_Tuple(Datatype *data, int row, int col);
        Datatype Get(int row, int col);

    private:
        SparseArray<Datatype> SA;
};

template<class DataType>
sparArray_Tuple<DataType> :: sparArray_Tuple(DataType *data, int row, int col){
    int count_tu=0;
    SA.mu = row;
    SA.nu = col;
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            if(*((int *)data + i*col + j)){
                SA.data[count_tu].item = *((int *)data + i*col + j);
                SA.data[count_tu].row = i+1;
                SA.data[count_tu].col = j+1;
                count_tu++;
            }
        }
    }
    SA.tu = count_tu;
}

template<class DataType>
DataType sparArray_Tuple<DataType> :: Get(int row, int col){
    for(int i=0; i<SA.tu; i++){
        if(SA.data[i].row == row && SA.data[i].col == col) return SA.data[i].item;
    }
    return 0;
}




int main(){
    int a[5][5] = {
        {0,0,5,0,0},
        {0,0,2,0,0},
        {0,0,0,0,1},
        {3,0,1,0,3},
        {0,0,0,0,7}
    };
    sparArray_Tuple<int> A((int*)a, 5, 5);

    cout << "通过压缩所得的三元组获取第2行第3列的数据：" << A.Get(2,3) << endl;
    cout << "通过压缩所得的三元组获取第3行第3列的数据：" << A.Get(3,3) << endl;
    cout << "通过压缩所得的三元组获取第5行第5列的数据：" << A.Get(5,5) << endl;

    int test;
    cin >> test;

    // A.Print_Extressed();

    // for(int i=0; i<5; i++){
    //     for(int j=0; j<5; j++){
    //         A.SetValue(a[i][j], i+1, j+1);
    //     }
    // }

    // for(int i=1; i<=5; i++){
    //     for(int j=1; j<=5; j++){
    //         cout << A.GetValue(i,j) << '\t';
    //     }
    //     cout << endl;
    // }

    // A.Compress();

    // cout << endl;

    // A.Print_Extressed();

}